package com.demo.util;

import java.util.Arrays;
import java.util.Objects;

/**
 * @author lee9213@163.com
 * @version 1.0
 * @date 2018-05-09 21:35
 */
public class Quicksort {
    private int[] numbers;
    private int number;

    public void sort(int[] values) {
        // 检查数组是否为空
        if (values == null || values.length == 0) {
            return;
        }
        this.numbers = values;
        number = values.length;
        quicksort(0, number - 1);
    }

    private void quicksort(int low, int high) {
        int i = low, j = high;
        // 把数组中间的元素设置为基准数
        int pivot = numbers[low + (high - low) / 2];

        // 分开成两个数组
        while (i <= j) {
            //从左向右“探测”，如果左边的元素小于基准数，则去“探测”下一个元素
            while (numbers[i] < pivot) {
                i++;
            }
            //从右向左“探测”，如果左边的元素大于基准数，则去“探测”下一个元素
            while (numbers[j] > pivot) {
                j--;
            }

            // 如果左边探测结果大于基准数，右边探测结果小于基准数，那么交换这两个元素
            // 然后继续探测
            if (i <= j) {
                exchange(i, j);
                i++;
                j--;
            }
        }
        // 递归
        if (low < j) {
            quicksort(low, j);
        }
        if (i < high) {
            quicksort(i, high);
        }
    }

    private void exchange(int i, int j) {
        int temp = numbers[i];
        numbers[i] = numbers[j];
        numbers[j] = temp;
    }

    public static void sort(int[] values, int low, int high) {
        if (Objects.isNull(values) || values.length == 0) {
            return;
        }
        if (low > high) {
            return;
        }
        int i = low, j = high;
        int pivot = values[low + (high - low) / 2];
        while (i <= j) {

            while (values[i] < pivot) {
                i++;
            }
            while (values[j] > pivot) {
                j--;
            }

            if (i <= j) {
                int temp = values[i];
                values[i] = values[j];
                values[j] = temp;
            }
        }

        if (low < j) {
            sort(values, low, j);
        }
        if (high > i) {
            sort(values, i, high);
        }
    }

    public static void main(String[] args) {
        int[] values = {8, 4, 7, 2, 1, 9, 12, 74, 13, 93};
        sort(values,0,values.length-1);
        Arrays.stream(values).forEach(i -> System.out.println(i));
    }
}
